package leetcode100;

// TODO 动态规划 | 状态转移方程 [困难] 【-】 不同的二叉搜索树
// TODO https://leetcode.cn/problems/unique-binary-search-trees/solution/hua-jie-suan-fa-96-bu-tong-de-er-cha-sou-suo-shu-b/

public class lc100_0096 {

    public int numTrees(int n) {
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        // 求 dp[i]: i 个结点可以构建的 BST 数目
        for (int i = 2; i <= n; ++i) {
            for (int j = 1; j <= i; ++j) {
                dp[i] += dp[j - 1] * dp[i - j];
            }
        }

        return dp[n];
    }

}
